package leetcode.每日一题;

import org.junit.Test;

import java.time.temporal.ValueRange;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * @author ：zsy
 * @date ：Created 2021/6/19 14:13
 * @description：
 */
public class 串联字符串的最大长度 {

    @Test
    public void Test() {
        Solution solution = new Solution();
        int i = solution.maxLength(Arrays.asList(new String[]{"abcdefghijklmnopqrstuvwxyz"}));
        System.out.println(i);
    }

    class Solution {
        List<String> arr;
        int maxLen = Integer.MIN_VALUE;
        public int maxLength(List<String> arr) {
            this.arr = arr;
            dfs(new StringBuilder(), 0, new int[26]);
            return maxLen;
        }
        private void dfs(StringBuilder builder, int index, int[] count) {
            maxLen = Math.max(maxLen, builder.length());
            if (index == arr.size()) return;
            //拿
            char[] chars = arr.get(index).toCharArray();
            boolean ok = true;
            int[] curCount = Arrays.copyOf(count, count.length);
            for (char c : chars) {
                if (curCount[c - 'a'] == 1) {
                    ok = false;
                    break;
                } else {
                    curCount[c - 'a']++;
                }
            }
            if (ok) {
                dfs(new StringBuilder(builder).append(arr.get(index)),index + 1, curCount);
            }
            //不拿
            dfs(builder, index + 1, count);
        }
    }
}
